package com.kehao.leetcode.hard.tree_graph;

import org.junit.Test;

import java.util.*;

public class LadderLengthSolution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashMap<String,Integer> map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        map.put(beginWord,1);
        while (!queue.isEmpty()){
            String poll = queue.poll();
            if(endWord.equals(poll)){
                return map.get(poll);
            }
            for (int i = 0; i < wordList.size(); i++) {
                if(ACharDiff(poll,wordList.get(i))){
                    if(!map.containsKey(wordList.get(i))){
                        queue.add(wordList.get(i));
                        map.put(wordList.get(i),map.get(poll)+1);
                    }
                }
            }
        }
        return 0;
    }

    private boolean ACharDiff(String str1,String str2){
        int diffcount = 0;
        int size = Math.min(str1.length(),str2.length());
        for (int i = 0; i < size; i++) {
            if(str1.charAt(i)!=str2.charAt(i)) {
                diffcount++;
            }
        }

        return diffcount==1;
    }

    @Test
    public void test01(){
        String beginWord = "hit", endWord = "cog";
        String [] wordList = {"hot","dot","dog","lot","log","cog"};
        int result = ladderLength(beginWord, endWord, Arrays.asList(wordList));
        System.out.println(result);
    }

    @Test
    public void test02(){
        String beginWord = "hit", endWord = "cog";
        String [] wordList = {"hot","dot","dog","lot","log"};
        int result = ladderLength(beginWord, endWord, Arrays.asList(wordList));
        System.out.println(result);
    }
}
